package leetcode.N1_N100;

import java.util.Arrays;
import java.util.Objects;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/10/19 3:31 下午
 */
public class N43 {

    public static void main(String[] args) {
        String num1 = "123";
        String num2 = "456";
        System.out.println(multiply(num1, num2));
    }

    public static String multiply(String num1, String num2) {
        // 理性输入
        if (num1 == null || Objects.equals(num1, "0")
         || num2 == null || Objects.equals(num2, "0")
        ) {
            return "0";
        }
        // 最大结果为222位 十进制
        int[] result = new int[num1.length() + num2.length() + 2];
        int[] num2Array = new int[num2.length()];

        for (int i = 0; i < num2.length(); i++) {
            num2Array[num2.length() - 1 - i] = num2.charAt(i) - '0';
        }

        for (int i = 0; i < num1.length(); i++) {
            // 模拟乘法
            int[] currentResult = simpleMultiply(num2Array, num1.charAt(num1.length() - 1- i) - '0');
            // 累加结果
            addResult(result, currentResult, i);
        }

        // 输出结果
        StringBuilder sb = new StringBuilder();
        for (int j = result.length - 1; j >= 0; j--) {
            if (result[j] == 0 && sb.length() == 0) {
                continue;
            }
            sb.append(result[j]);
        }
        return sb.toString();
    }

    private static void addResult(int[] result, int[] currentResult, int val) {
        int add = 0;
        for (int i = 0; i < currentResult.length; i++) {
            int temp = currentResult[i] + result[i + val] +  + add;
            if (temp >= 10) {
                add = 1;
                result[i + val] = temp % 10;
            } else {
                add = 0;
                result[i + val] = temp;
            }
        }
    }

    private static int[] simpleMultiply(int[] num, int val) {
        int[] result = new int[num.length + 1];
        int add = 0;
        for (int i = 0; i < num.length; i++) {
            int temp = num[i] * val + add;

            if (temp < 10) {
                result[i] = temp;
                add = 0;
            } else {
                add = temp / 10;
                result[i] = temp % 10;
            }
        }
        result[num.length] = add;
        return result;
    }

}
